package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1044 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 什么玩意，完全看不懂
     * @return:
     */
    class Solution {
        final long[] POW = new long[30001];

        public String longestDupSubstring(String s) {
            // 预处理31的x次幂
            POW[0] = 1;
            for (int x = 1; x <= 30000; ++x) POW[x] = 31 * POW[x - 1];

            int n = s.length(), end = 0;
            // hash[i] = s[0]*31^i + s[1]*31^(i-1) + ... + s[i]*31^0
            long[] hash = new long[n];
            long h = 0;

            for (int i = 0; i < n; ++i) hash[i] = h = 31 * h + s.charAt(i);

            Set<Long> set = new HashSet<>();
            int low = 1, high = n;

            while (low <= high) {
                int mid = low + high >>> 1, i = mid - 1;
                for (set.clear(); i < n; ++i) {// 枚举右边界
                    // s[i-mid+1, i] 的哈希值
                    h = hash[i] - (i >= mid ? hash[i - mid] * POW[mid] : 0);
                    if (!set.add(h)) break;// 出现重复的哈希值
                }
                if (i == n) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                    end = i + 1;
                }
            }
            return s.substring(end - high, end);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1044 an = new LC1044();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
